package com.lanluo.service.structure;

/**
 * 符号表（基于有序数组 二分查找）
 * @author
 * @date 2018-08-29-16:21
 */
public class BinarySearchST<Key extends Comparable<Key>, Value> {
    private Key[] keys;
    private Value[] vals;
    private int N;

    public BinarySearchST(int capacity) {
        keys = (Key[]) new Comparable[capacity];
        vals = (Value[]) new Object[capacity];
    }

    /**
     * 从有序数组中查找键
     * @param key
     * @return 返回该键在数组中的位置，如果不在数组中返回该键应该在数组中的位置（根据从小到大的顺序）
     */
    public int rank(Key key) {
        int lo = 0,hi = N-1;
        while (lo <= hi) {
            int mid = lo + (hi - lo)/2;
            int cmp = key.compareTo(keys[mid]);
            if      (cmp<0) hi = mid -1;
            else if (cmp>0) lo = mid +1;
            else return mid;
        }
        return lo;
    }

    /**
     *  存入的键是有序的
     * @param key
     * @param val
     */
    public void put(Key key, Value val) {
        //获取该键所在位置
        int i = rank(key);
        //如果该键在数组中，覆盖该键键所在的值
        if(i < N && keys[i].compareTo(key) == 0) {
            vals[i] = val;
            return;
        }
        //如果该键不在数组中，将该键应该所在位置之后的元素向后移一位，将该键放入所在位置
        for (int j = N; j>i; j--) {
            keys[j] = keys[j-1];
            vals[j] = vals[j-1];
        }
        keys[i] = key;
        vals[i] = val;
        N++;
    }

    public Value get(Key key) {
        if(isEmpty()) return null;
        int i = rank(key);
        if(i < N && keys[i].compareTo(key) == 0)
            return vals[i];
        else
            return null;
    }

    public boolean isEmpty() {
        return N < 1;
    }

    public void printKeys() {
        for (int i = 0; i < N; i++) {
            System.out.println(keys[i]);
        }
    }

    public void printVals() {
        for (int i = 0; i < N; i++) {
            System.out.println(vals[i]);
        }
    }

    public static void main(String[] args) {
        BinarySearchST<String, String> bsst = new BinarySearchST<String, String>(10);

        bsst.put("b", "的");
        bsst.put("a", "我");
        bsst.put("c", "世");
        bsst.put("e", "啊");
        bsst.put("d", "界");
        //存入时无序，取出时有序
        System.out.println(bsst.get("e"));
        bsst.printKeys();
    }

}